package divide;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int divide(int a, int b) {
        // 找  15 / 2 有2^n个b 然后再看余数里面有2的多少次方个b
        int neg = 1;
        if(a<0&&b>0||a>0&&b<0){
            neg = -1;
        }
//        if(a==Integer.MIN_VALUE&&b==-1){
//            return Integer.MAX_VALUE;
//        }
//        if(a==Integer.MIN_VALUE&&b==1){
//            return Integer.MIN_VALUE;
//        }
        long aa = Math.abs((long)a);
        long bb = Math.abs((long)b);
        List<Integer> list = new ArrayList<>();
        list.add(0);
        int index = 0;
        while(aa>bb){
            // res<<2(相当于*2)
            // 11
            // 110
            long tmp = bb<<(list.get(index)+1);
            if(tmp>aa){
                // 表明最多有2^res 个b相加小于等于a
                // 再看余数里面有好多个2^n 个 b等于余数
                aa = aa - (bb<<list.get(index));
                index++;
                list.add(0);
            }else{
                list.set(index,list.get(index)+1);
            }
        }
        int res = 0;
        for (int i = 0; i < list.size(); i++) {
            res += Math.pow(2,list.get(i));
        }
        return aa<bb?(res-1)*neg:res*neg;
    }
}
